#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath> // for pow

using namespace std;

struct Path {
    vector<size_t> nodes;
    size_t length;
    bool operator>(const Path& other) const {
        return length > other.length;
    }
};

// Dijkstra算法，找到从起点到终点的最短路径
vector<size_t> dijkstra(size_t start, size_t end, const vector<vector<size_t>>& roadlength) {
    const size_t INF = INT_MAX;
    vector<size_t> dist(roadlength.size(), INF);
    dist[start] = 0;
    vector<size_t> prev(roadlength.size(), INF);
    priority_queue<pair<size_t, size_t>, vector<pair<size_t, size_t>>, greater<pair<size_t, size_t>>> pq;
    pq.push({0, start});
    while (!pq.empty()) {
        size_t u = pq.top().second;
        size_t d = pq.top().first;
        pq.pop();
        if (u == end) break;
        if (d > dist[u]) continue;
        for (size_t v = 0; v < roadlength.size(); ++v) {
            if (roadlength[u][v] != INF && dist[v] > dist[u] + roadlength[u][v]) {
                dist[v] = dist[u] + roadlength[u][v];
                prev[v] = u;
                pq.push({dist[v], v});
            }
        }
    }
    if (dist[end] == INF) return vector<size_t>();
    vector<size_t> path;
    for (size_t current = end; current != start; current = prev[current]) {
        path.push_back(current);
        if (prev[current] == INF) break;
    }
    path.push_back(start);
    reverse(path.begin(), path.end());
    return path;
}

// Yen's Algorithm，找到前k条最短路径
vector<vector<size_t>> yen_ksp(size_t start, size_t end, size_t k, const vector<vector<size_t>>& roadlength) {
    vector<vector<size_t>> P;
    if (k <= 0) return P;

    // 找到第一条最短路径
    vector<size_t> path = dijkstra(start, end, roadlength);
    if (path.empty()) return P;
    P.push_back(path);

    // 优先队列，存储候选路径
    priority_queue<Path, vector<Path>, greater<Path>> Q;

    // 生成偏离路径
    for (size_t i = 0; i < P[0].size() - 1; ++i) {
        size_t r = P[0][i];
        size_t s = P[0][i + 1];

        // 修改道路长度，禁止使用当前路径中的边
        vector<vector<size_t>> modified_roadlength = roadlength;
        modified_roadlength[r][s] = INT_MAX;
        modified_roadlength[s][r] = INT_MAX;

        // 找到从 r 到 end 的最短路径
        vector<size_t> new_path = dijkstra(r, end, modified_roadlength);
        if (!new_path.empty()) {
            // 合并路径
            vector<size_t> combined_path(P[0].begin(), P[0].begin() + i + 1);
            combined_path.insert(combined_path.end(), new_path.begin(), new_path.end());

            // 计算路径长度
            size_t length = 0;
            for (size_t j = 0; j < combined_path.size() - 1; ++j) {
                length += roadlength[combined_path[j]][combined_path[j + 1]];
            }

            // 将候选路径加入优先队列
            Q.push({combined_path, length});
        }
    }

    // 继续搜索，直到找到 k 条路径或没有更多路径
    while (!Q.empty() && P.size() < k) {
        Path candidate = Q.top();
        Q.pop();

        // 检查是否已经存在相同的路径
        bool is_duplicate = false;
        for (const auto& p : P) {
            if (p == candidate.nodes) {
                is_duplicate = true;
                break;
            }
        }

        if (!is_duplicate) {
            P.push_back(candidate.nodes);

            // 生成新的偏离路径
            for (size_t i = 0; i < candidate.nodes.size() - 1; ++i) {
                size_t r = candidate.nodes[i];
                size_t s = candidate.nodes[i + 1];

                // 修改道路长度，禁止使用当前路径中的边
                vector<vector<size_t>> modified_roadlength = roadlength;
                modified_roadlength[r][s] = INT_MAX;
                modified_roadlength[s][r] = INT_MAX;

                // 找到从 r 到 end 的最短路径
                vector<size_t> new_path = dijkstra(r, end, modified_roadlength);
                if (!new_path.empty()) {
                    // 合并路径
                    vector<size_t> combined_path(candidate.nodes.begin(), candidate.nodes.begin() + i + 1);
                    combined_path.insert(combined_path.end(), new_path.begin(), new_path.end());

                    // 计算路径长度
                    size_t length = 0;
                    for (size_t j = 0; j < combined_path.size() - 1; ++j) {
                        length += roadlength[combined_path[j]][combined_path[j + 1]];
                    }

                    // 将候选路径加入优先队列
                    Q.push({combined_path, length});
                }
            }
        }
    }

    return P;
}

// 计算路径的总长度
size_t calculatePathLength(const vector<size_t>& path, const vector<vector<size_t>>& roadlength) {
    size_t length = 0;
    for (size_t i = 0; i < path.size() - 1; ++i) {
        length += roadlength[path[i]][path[i+1]];
    }
    return length;
}

// 检测当前车辆路径组合是否会导致堵车
struct Event {
    size_t time;
    size_t u; // 起始节点
    size_t v; // 结束节点
    bool enter; // 进入路段（true）还是离开路段（false）
    // 重载比较运算符，使优先队列按时间升序排列
    bool operator>(const Event& other) const {
        return time > other.time;
    }
};

bool checkTraffic(const vector<vector<size_t>>& combination,
                  const vector<vector<size_t>>& roadlength,
                  const vector<vector<size_t>>& restrictions) {
    // 创建优先队列，存储事件
    priority_queue<Event, vector<Event>, greater<Event>> eventQueue;

    // 初始化事件队列
    for (const vector<size_t>& path : combination) {
        size_t current_time = 0;
        for (size_t i = 1; i < path.size(); ++i) {
            size_t u = path[i - 1];
            size_t v = path[i];
            size_t length = roadlength[u][v];
            eventQueue.push({current_time, u, v, true}); // 进入事件
            eventQueue.push({current_time + length, u, v, false}); // 离开事件
            current_time += length;
        }
    }

    // 维护当前每条道路的流量
    vector<vector<size_t>> current_flow(roadlength.size(), vector<size_t>(roadlength.size(), 0));

    while (!eventQueue.empty()) {
        size_t current_time = eventQueue.top().time;
        vector<Event> same_time_events;
        // 取出所有时间等于current_time的事件
        while (!eventQueue.empty() && eventQueue.top().time == current_time) {
            same_time_events.push_back(eventQueue.top());
            eventQueue.pop();
        }
        // 先处理离开事件
        for (Event& event : same_time_events) {
            if (!event.enter) {
                if (current_flow[event.u][event.v] > 0) {
                    current_flow[event.u][event.v]--;
                    current_flow[event.v][event.u]--;
                }
            }
        }
        // 再处理进入事件
        for (Event& event : same_time_events) {
            if (event.enter) {
                current_flow[event.u][event.v]++;
                current_flow[event.v][event.u]++;
                if (current_flow[event.u][event.v] > restrictions[event.u][event.v]) {
                    return false; // 堵车
                }
            }
        }
    }

    // 所有事件处理完毕，没有堵车
    return true;
}

// 计算当前组合的总路径长度
size_t calculateTotalLength(const vector<vector<size_t>>& combination, const vector<vector<size_t>>& roadlength) {
    size_t total_length = 0;
    for (const vector<size_t>& path : combination) {
        for (size_t i = 1; i < path.size(); i++) {
            size_t u = path[i - 1];
            size_t v = path[i];
            total_length += roadlength[u][v];
        }
    }
    return total_length;
}

// 遍历所有车辆路径组合的函数
void traverseCombinations(const vector<vector<vector<size_t>>>& all_cars_paths, size_t car_index, vector<vector<size_t>>& current_combination, const vector<vector<size_t>>& roadlength, const vector<vector<size_t>>& restrictions, vector<vector<size_t>>& best_combination, size_t& min_total_length) {
    // 如果已经处理完所有车辆，检查当前组合是否最优
    if (car_index == all_cars_paths.size()) {
        if (checkTraffic(current_combination, roadlength, restrictions)) {
            size_t total_length = calculateTotalLength(current_combination, roadlength);
            if (total_length < min_total_length) {
                min_total_length = total_length;
                best_combination = current_combination;
            }
        }
        return;
    }

    // 遍历当前车辆的所有路径方案
    for (const vector<size_t>& path : all_cars_paths[car_index]) {
        current_combination.push_back(path); // 选择当前路径方案
        traverseCombinations(all_cars_paths, car_index + 1, current_combination, roadlength, restrictions, best_combination, min_total_length); // 递归处理下一辆车
        current_combination.pop_back(); // 回溯，撤销选择
    }
}

// 找到不堵车且总路径长度最短的组合
void findBestCombination(const vector<vector<vector<size_t>>>& all_cars_paths, const vector<vector<size_t>>& roadlength, const vector<vector<size_t>>& restrictions) {
    vector<vector<size_t>> best_combination; // 存储最短组合
    size_t min_total_length = INT_MAX; // 记录最短组合的总路径长度

    // 遍历所有车辆路径组合
    vector<vector<size_t>> current_combination;
    traverseCombinations(all_cars_paths, 0, current_combination, roadlength, restrictions, best_combination, min_total_length);

    // 输出最短组合
    if (!best_combination.empty()) {
        cout << "Best combination (total length: " << min_total_length << "):" << endl;
        for (size_t i = 0; i < best_combination.size(); i++) {
            cout << "Car " << i + 1 << " path: ";
            for (size_t node : best_combination[i]) {
                cout << node + 1 << " ";
            }
            cout << endl;
        }
    } else {
        cout << "No valid combination found!" << endl;
    }
}

int main() {
    size_t N, M;
    cin >> N >> M;

    // 动态分配二维数组
    vector<vector<size_t>> roadlength(N, vector<size_t>(N, INT_MAX)); // 存储道路长度
    vector<vector<size_t>> restrictions(N, vector<size_t>(N)); // 存储道路的流量限制
    vector<vector<size_t>> cars(M, vector<size_t>(2)); // 存储每辆车的起点和终点

    // 读取道路长度
    for (size_t i = 0; i < N; i++) {
        for (size_t j = 0; j < N; j++) {
            cin >> roadlength[i][j];
            if (roadlength[i][j] == 0 && i != j) {
                roadlength[i][j] = INT_MAX; // 如果道路长度为 0，则距离为无穷大
            }
        }
    }

    // 读取道路的流量限制
    for (size_t i = 0; i < N; i++) {
        for (size_t j = 0; j < N; j++) {
            cin >> restrictions[i][j];
        }
    }

    // 读取每辆车的起点和终点
    for (size_t i = 0; i < M; i++) {
        cin >> cars[i][0] >> cars[i][1];
        cars[i][0]--; // 将输入的起点和终点转换为从 0 开始的索引
        cars[i][1]--;
    }

    // 计算k的值
    size_t k = (size_t)pow(SIZE_MAX, 1.0 / M);

    // 存储每辆车的前k条最短路径
    vector<vector<vector<size_t>>> all_cars_paths(M);

    // 为每辆车找到前k条最短路径
    for (size_t i = 0; i < M; i++) {
        size_t start = cars[i][0];
        size_t end = cars[i][1];
        all_cars_paths[i] = yen_ksp(start, end, k, roadlength);
    }

    // 找到不堵车且总路径长度最短的组合
    findBestCombination(all_cars_paths, roadlength, restrictions);

    return 0;
}